package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.List;

public class Subsets {

    /**
     * 位运算
     * 将数组元素在子集中出现记为 1, 未出现记为0
     * 这样我们就可以用一个长度为n的二进制数来表示子集（n 代表数组长度）
     * 开始我们将二进制数记为0，表示空集，
     * 然后不断 + 1， 获取子集，一直到n位二进制全部是1为止
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int len = nums.length, max = 1 << len;
        for (int i = 0; i < max; ++i){
            List<Integer> subList = new ArrayList<>();
            for (int j = 0; j < len; ++j){
                int t = 1 << j;
                if (i < t){
                    break;
                }
                if ((i & t) > 0){
                    subList.add(nums[j]);
                }
            }
            list.add(subList);
        }
        return list;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        List<List<Integer>> subsets = new Subsets().subsets(nums);
        PrintUtils.println(subsets);
    }

}
